import java.util.*;

public class DictionaryTrie implements BookTrie {
    static int nextBookId = 0;

    HashMap<String, DictionaryTrie> dictionary = new HashMap<String,DictionaryTrie>();
    boolean isFinalMark = false;
    List<BookTrieInfo> books = new ArrayList<BookTrieInfo>();

    ArrayList<String> prefix = new ArrayList<String>();

    private DictionaryTrie add(String word) {
        if (!dictionary.containsKey(word)){
            dictionary.put(word, new DictionaryTrie());
        }
        return dictionary.get(word);
    }

    public BookTrieInfo add(String[] authors, String[] title){
        DictionaryTrie trie = this;
        for (String word : title) {
            trie = trie.add(word);
        }

        BookTrieInfo book = new BookTrieInfo();
        book.bookId = nextBookId++;
        book.title = title;
        book.authors = authors;

        trie.isFinalMark = true;
        trie.books.add(book);

        return book;
    }

    public void add(String[] title, BookTrieInfo book) {
        DictionaryTrie trie = this;
        for (String word : title) {
            trie = trie.add(word);
        }
        trie.isFinalMark = true;
        trie.books.add(book);
    }

    private DictionaryTrie copy() {
        DictionaryTrie copy = new DictionaryTrie();
        copy.dictionary = dictionary;
        copy.isFinalMark = isFinalMark;
        copy.books = books;
        return copy;
    }

    public BookTrie getSubTrie(String word) {
        if (!dictionary.containsKey(word)) return null;
        DictionaryTrie trie = dictionary.get(word).copy();
        trie.prefix = new ArrayList<String>(prefix);
        trie.prefix.add(word);
        return trie;
    }

    public List<String> getPrefix() {
        return prefix;
    }

    public boolean isFinal() {
        return isFinalMark;
    }

    public List<BookTrieInfo> getBooks() {
        return books;
    }
}
